package my.jwds.p230;

import my.jwds.p94.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class KthSmallest {

    public static void main(String[] args) {
        KthSmallest obj = new KthSmallest();
        Integer arr[] = {3,1,4,null,2};
        TreeNode root = TreeNode.to_binaryHaveNull(arr);
        System.out.println(obj.kthSmallest(root,1));
    }
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        kthSmallest(root,values,k);
        return values.get(k-1);
    }

    public void kthSmallest(TreeNode root, List<Integer> values,int k) {
        if (root.left != null){
            kthSmallest(root.left,values,k);
            if (values.size() >= k){
                return;
            }
        }
        values.add(root.val);
        if (values.size() >= k){
            return;
        }
        if (root.right != null){
            kthSmallest(root.right,values,k);
            if (values.size() >= k){
                return;
            }
        }
    }
}
